#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020/4/17 21:01|21:01
# @Author  : yangdingyi
# @File    : 55. 跳跃游戏.2020-04-17
# @Software: PyCharm
from typing import List


class Solution:
    def canJump(self, nums: List[int]) -> bool:
        ll = len(nums)
        # a = [False for i in range(ll)]
        # a[0] = True
        # for i in range(ll):
        #     if a[i]:
        #         for j in range(i+1, min(i + nums[i] + 1, ll)):
        #             a[j] = True
        # return a[ll - 1]
        mm = 0
        for i in range(ll):
            if i <= mm:
                if i + nums[i] > mm:
                    mm = i + nums[i]
        return ll - 1 <= mm


solve = Solution()
nn = [2, 3, 1, 1, 4]
print(nn)
print(solve.canJump(nn))
